package com.leetcode.算法策略相关.动态规划;

import java.util.Arrays;
import java.util.HashSet;

/**
 * @author: ZhouBert
 * @date: 2021/2/5
 * @description: 322. 零钱兑换
 * https://leetcode-cn.com/problems/coin-change/
 */
public class B_322_零钱兑换 {

	public static void main(String[] args) {

		B_322_零钱兑换 action = new B_322_零钱兑换();
		test1(action);
		test2(action);
		test3(action);
		test4(action);
		test5(action);
		test6(action);
	}

	public static void test1(B_322_零钱兑换 action) {
		//3
		int[] coins = new int[]{1, 2, 5};
		int amount = 11;
		int res = action.coinChange(coins, amount);
		System.out.println("res = " + res);
	}

	public static void test2(B_322_零钱兑换 action) {
		//-1
		int[] coins = new int[]{2};
		int amount = 3;
		int res = action.coinChange(coins, amount);
		System.out.println("res = " + res);
	}

	public static void test3(B_322_零钱兑换 action) {
		//0
		int[] coins = new int[]{1};
		int amount = 0;
		int res = action.coinChange(coins, amount);
		System.out.println("res = " + res);
	}

	public static void test4(B_322_零钱兑换 action) {
		//1
		int[] coins = new int[]{1};
		int amount = 1;
		int res = action.coinChange(coins, amount);
		System.out.println("res = " + res);
	}

	public static void test5(B_322_零钱兑换 action) {
		//2
		int[] coins = new int[]{1};
		int amount = 2;
		int res = action.coinChange(coins, amount);
		System.out.println("res = " + res);
	}

	public static void test6(B_322_零钱兑换 action) {
		//2
		int[] coins = new int[]{1, 2147483647};
		int amount = 2;
		int res = action.coinChange(coins, amount);
		System.out.println("res = " + res);
	}

	/**
	 * 每一轮硬币兑换的值可以看作是 所有减去能兑换的硬币的方案的硬币的最小值 + 1
	 * dp[amount] = min(dp[amount-coins[i1],dp[amount-coins[i2],...])+1
	 * 但是 当括号里都是 0 的时候，就直接返回 0
	 *
	 * @param coins
	 * @param amount
	 * @return
	 */
	public int coinChange(int[] coins, int amount) {
		//1.边界判断
		if (amount == 0) {
			return 0;
		}
		//对硬币进行升序
		Arrays.sort(coins);
		if (amount < coins[0]) {
			//如果目标小于 最小的硬币数
			return -1;
		}
		int size = amount + 1;
		int len = coins.length;
		int[] dpCoin = new int[size];
		HashSet<Integer> set = new HashSet<>();


		//region	从逆序出发（对于 coin[ix]=1 的情况，还不如从顺序出发）
		//如果从 dpCoin 的正序出发，就会有很多多余的计算，所以考虑从逆序出发
		//假设有一个方法可以得出 最少的数量

		//2.初始化
//		for (int i = 0; i < len; i++) {
//			set.add(coins[i]);
//			if (coins[i] < size) {
//				dpCoin[coins[i]] = 1;
//			}
//		}
//		dpCoin[amount] = getMinCoins(set, coins, len, dpCoin, amount);
//		if (dpCoin[amount] == 0 || dpCoin[amount] == -1) {
//			return -1;
//		}
//		return dpCoin[amount];
		//endregion

		//region	从顺序出发

		for (int i = 0; i < len; i++) {
			set.add(coins[i]);
		}
		dpCoin[0] = 0;
		for (int i = 1; i < size; i++) {
			if (set.contains(i)) {
				dpCoin[i] = 1;
				continue;
			}
			int res = Integer.MAX_VALUE;
			for (int j = 0; j < len; j++) {
				int value = i - coins[j];
				if (value < 0) {
					break;
				}
				if (dpCoin[value] != -1) {
					res = Math.min(res, dpCoin[value] + 1);
				}
			}
			if (res == Integer.MAX_VALUE) {
				dpCoin[i] = -1;
			} else {
				dpCoin[i] = res;
			}
		}

		//endregion
		return dpCoin[amount];
	}

	/**
	 * 逆序去获取结果
	 * 需要去获取非 0 的最小值
	 *
	 * @param set
	 * @param coins
	 * @param len    硬币的数量
	 * @param dpCoin
	 * @param amount
	 * @return
	 */
	private int getMinCoins(HashSet<Integer> set, int[] coins, int len, int[] dpCoin, int amount) {
		int res = Integer.MAX_VALUE;
		if (set.contains(amount)) {
			return 1;
		}
		for (int i = len - 1; i >= 0; i--) {
			int index = amount - coins[i];
			if (index < 0) {
				continue;
			}

			int v = getMinCoins(set, coins, len, dpCoin, amount - coins[i]);
			if (v != 0 && v != -1) {
				res = Math.min(v + 1, res);
			}
		}
		if (res == Integer.MAX_VALUE) {
			dpCoin[amount] = -1;
			return 0;
		}
		dpCoin[amount] = res;
		return res;
	}
}
